\relax 
\catcode`"\active
\select@language{english}
\@writefile{toc}{\select@language{english}}
\@writefile{lof}{\select@language{english}}
\@writefile{lot}{\select@language{english}}
\select@language{brazil}
\@writefile{toc}{\select@language{brazil}}
\@writefile{lof}{\select@language{brazil}}
\@writefile{lot}{\select@language{brazil}}
\select@language{brazil}
\@writefile{toc}{\select@language{brazil}}
\@writefile{lof}{\select@language{brazil}}
\@writefile{lot}{\select@language{brazil}}
\select@language{english}
\@writefile{toc}{\select@language{english}}
\@writefile{lof}{\select@language{english}}
\@writefile{lot}{\select@language{english}}
\@writefile{toc}{\contentsline {chapter}{List of Figures}{vii}}
\@writefile{toc}{\contentsline {chapter}{List of Tables}{x}}
\@writefile{toc}{\contentsline {chapter}{Abbreviations and Symbols}{xiii}}
\citation{BOSER92a}
\citation{VAPNIK9501}
\citation{VAPNIK9501}
\citation{VAPNIK9801}
\citation{CRISTIANINI0001}
\citation{CAMPBELL0201}
\@writefile{toc}{\contentsline {chapter}{\numberline {1}Introduction}{5}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\@writefile{toc}{\contentsline {section}{\numberline {1.1}Overview}{5}}
\citation{Drucker99}
\citation{Barzilay99}
\citation{KIM0201}
\citation{Brown00}
\citation{VALENTINI0201}
\citation{Joachims98}
\citation{DISTANTE0301}
\citation{KOTROPOULOS0301}
\citation{SHAONING0301}
\citation{WANG0201}
\citation{JEFFREY0201}
\citation{VAPNIK9801}
\citation{LOO0201}
\@writefile{toc}{\contentsline {section}{\numberline {1.2}Motivations}{6}}
\citation{MCQUENN67}
\citation{ANDERBERG73}
\citation{Lloyd82}
\citation{BARROS2000A}
\citation{dudahart73}
\@writefile{toc}{\contentsline {section}{\numberline {1.3}Contributions}{7}}
\citation{CACHIN9401}
\citation{Luenberger86}
\citation{barros:2001}
\@writefile{toc}{\contentsline {section}{\numberline {1.4}Outline of the chapters}{9}}
\citation{VAPNIK9801}
\citation{VLADIMIR9801}
\@writefile{toc}{\contentsline {chapter}{\numberline {2}Statistical learning}{11}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{CAP-LEARN-GER}{{2}{11}}
\@writefile{toc}{\contentsline {section}{\numberline {2.1}Introduction}{11}}
\@writefile{toc}{\contentsline {section}{\numberline {2.2}Machine learning}{11}}
\citation{VAPNIK9801}
\citation{VAPNIK9801}
\citation{VLADIMIR9801}
\@writefile{lof}{\contentsline {figure}{\numberline {2.1}{\ignorespaces Machine learning diagram.\relax }}{12}}
\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
\newlabel{FIG-LEARN-MACHINE}{{2.1}{12}}
\citation{VLADIMIR9801}
\@writefile{toc}{\contentsline {section}{\numberline {2.3}Learning process}{13}}
\@writefile{toc}{\contentsline {section}{\numberline {2.4}Risk functional}{13}}
\citation{VAPNIK9801}
\citation{VLADIMIR9801}
\citation{WING9101}
\newlabel{EQ-CAPLG-QUAD-LOSS}{{2.2}{14}}
\newlabel{EQ-CAPLG-INDICATOR}{{2.4}{14}}
\newlabel{EQ-CAPLG-RISK-FUNCT}{{2.5}{14}}
\citation{VAPNIK9801}
\citation{HAYKIN9901}
\@writefile{toc}{\contentsline {section}{\numberline {2.5}Empirical risk minimization principle}{15}}
\citation{VAPNIK8201}
\citation{VAPNIK9801}
\@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Expected convergence for the empirical risk when the number of vectors (p) becomes large (horizontal axis).\relax }}{16}}
\newlabel{FIG-LEARN-ERM-CONSISTENCY}{{2.2}{16}}
\newlabel{EQ-CAP2-CONV}{{2.8}{16}}
\citation{HAYKIN9901}
\citation{Burges98}
\citation{VAPNIK9801}
\@writefile{toc}{\contentsline {section}{\numberline {2.6}VC dimension}{17}}
\citation{VAPNIK9801}
\citation{Burges98}
\citation{VAPNIK9801}
\@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces VC dimension for linear indicator functions in a two-dimensional space}}{18}}
\newlabel{FIG-VCDIMENSION}{{2.3}{18}}
\@writefile{toc}{\contentsline {section}{\numberline {2.7}Structural risk minimization principle}{18}}
\newlabel{EQ-RISK-BOUND}{{2.10}{18}}
\@writefile{lof}{\contentsline {figure}{\numberline {2.4}{\ignorespaces Nested structures for different model complexities.\relax }}{19}}
\newlabel{FIG-LEARN-SRM}{{2.4}{19}}
\@writefile{toc}{\contentsline {section}{\numberline {2.8}Conclusion}{20}}
\citation{BOSER92a}
\citation{VAPNIK9501}
\citation{VAPNIK9501}
\@writefile{toc}{\contentsline {chapter}{\numberline {3}Support Vector Machines}{21}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{CAP-INTRO-SVM}{{3}{21}}
\@writefile{toc}{\contentsline {section}{\numberline {3.1}Introduction}{21}}
\citation{VAPNIK9501}
\citation{COVER6501}
\@writefile{toc}{\contentsline {section}{\numberline {3.2}SVMs with hard margins}{22}}
\newlabel{EQ-LIN-SEP}{{3.1}{22}}
\newlabel{EQ-HIPER-NON-LIN}{{3.2}{22}}
\citation{VAPNIK9801}
\citation{HAYKIN9901}
\citation{BAZARAA7901}
\@writefile{lof}{\contentsline {figure}{\numberline {3.1}{\ignorespaces Maximum margin separation hyper-plane}}{23}}
\newlabel{FIG-MAX-MARGIN}{{3.1}{23}}
\newlabel{EQ-CAP3-PRIMAL}{{3.3}{23}}
\newlabel{EQ-FORMA-LAGRAN-DUAL}{{3.5}{23}}
\newlabel{EQ-DERIV-PART-W}{{3.6}{23}}
\citation{VAPNIK9801}
\citation{HAYKIN9901}
\citation{VAPNIK9501}
\newlabel{EQ-DERIV-PART-B}{{3.7}{24}}
\newlabel{EQ-FORMA-DUAL}{{3.8}{24}}
\newlabel{EQ-CAP3-DUAL}{{3.9}{24}}
\@writefile{toc}{\contentsline {section}{\numberline {3.3}SVMs with soft margins}{24}}
\newlabel{EQ-LIN-SEP-FOLGA}{{3.10}{24}}
\citation{VAPNIK9801}
\citation{HAYKIN9901}
\newlabel{EQ-PRIMAL-SLACK}{{3.12}{25}}
\citation{VAPNIK9801}
\citation{HAYKIN9901}
\newlabel{EQ-FORMA-LAGRAN-DUAL-FOLGA}{{3.14}{26}}
\newlabel{EQ-DERIV-PART-W-FOLGA}{{3.15}{26}}
\newlabel{EQ-DERIV-PART-B-FOLGA}{{3.16}{26}}
\newlabel{EQ-DERIV-PART-E-FOLGA}{{3.17}{26}}
\newlabel{EQ-FORMA-DUAL-FOLGA}{{3.18}{26}}
\newlabel{EQ-DUAL-SLACK}{{3.19}{26}}
\citation{COURANT7001}
\citation{CRISTIANINI0001}
\@writefile{toc}{\contentsline {section}{\numberline {3.4}Implicit mapping using kernel functions}{27}}
\@writefile{lof}{\contentsline {figure}{\numberline {3.2}{\ignorespaces Mapping function $\boldsymbol  {\varphi }(\cdot )$ and the implicit mapping performed by kernel functions.\relax }}{27}}
\newlabel{FIG-MAX-IMPMAP}{{3.2}{27}}
\newlabel{EQ-KERNEL-MATRIX}{{3.21}{27}}
\citation{Kaufmann99}
\@writefile{lot}{\contentsline {table}{\numberline {3.1}{\ignorespaces Some types of functions that can be used as inner-product kernel\relax }}{28}}
\newlabel{TAB-KERNELTYPES}{{3.1}{28}}
\citation{Platt98b}
\citation{SMOBR}
\@writefile{toc}{\contentsline {section}{\numberline {3.5}An example}{29}}
\@writefile{lof}{\contentsline {figure}{\numberline {3.3}{\ignorespaces Training set for the checkerboard example. Classes are represented by circles and crosses symbols.\relax }}{29}}
\newlabel{FIG-EXE}{{3.3}{29}}
\@writefile{lof}{\contentsline {figure}{\numberline {3.4}{\ignorespaces Non-linear decision boundaries in the input space for checkerboard example. Support vectors are marked with a circle around vectors and the decision is represented by the continuous line. Dashed and dotted lines indicate the margins.\relax }}{30}}
\newlabel{FIG-EXE-DEC}{{3.4}{30}}
\@writefile{toc}{\contentsline {section}{\numberline {3.6}Conclusion}{30}}
\citation{Luenberger86}
\@writefile{toc}{\contentsline {chapter}{\numberline {4}Training SVMs}{31}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{CAP-SVM-TRAINING}{{4}{31}}
\@writefile{toc}{\contentsline {section}{\numberline {4.1}Introduction}{31}}
\@writefile{toc}{\contentsline {section}{\numberline {4.2}Optimality conditions and feasible regions}{32}}
\citation{SteveGun2000}
\citation{NetLib2000}
\citation{Vanderbei94}
\@writefile{lof}{\contentsline {figure}{\numberline {4.1}{\ignorespaces Geometric interpretation of support vectors}}{33}}
\newlabel{FIG-KKT}{{4.1}{33}}
\@writefile{toc}{\contentsline {section}{\numberline {4.3}Training methods for SVMs}{33}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3.1}Classical methods}{33}}
\citation{Suykens99a}
\citation{LAWSON9501}
\citation{Keerthi99b}
\citation{Zhang99a}
\@writefile{lof}{\contentsline {figure}{\numberline {4.2}{\ignorespaces Feasible region for a 3D case}}{34}}
\newlabel{FIG-FEASIBLE-REGION}{{4.2}{34}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3.2}Geometric methods}{34}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3.3}Iterative methods}{35}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.3.1}Gradient ascent}{35}}
\newlabel{EQ-TRAIN-SVM-QP-BASIC}{{4.1}{35}}
\newlabel{EQ-TRAIN-AN-EVIDENCE}{{4.2}{35}}
\citation{CRISTIANINI0001}
\citation{CRISTIANINI0001}
\newlabel{EQ-TRAIN-DERIV-AN}{{4.4}{36}}
\newlabel{EQ-TRAIN-ANEW}{{4.6}{36}}
\newlabel{EQ-TRAIN-OUTPUT-GRAD}{{4.8}{37}}
\newlabel{EQ-TRAIN-ANEW2}{{4.9}{37}}
\newlabel{EQ-TRAIN-ERROR-EXPRE}{{4.10}{37}}
\newlabel{EQ-ANEW-FINAL}{{4.3.3.1}{37}}
\newlabel{EQ-TRAIN-ANEW-ETA}{{4.11}{37}}
\citation{Adatron98}
\citation{FriCriCam98}
\citation{Mangasarian99}
\citation{ManMus99}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.3.2}Successive Over Relaxation}{38}}
\newlabel{CAP-SEC-TRAIN-SOR}{{4.3.3.2}{38}}
\newlabel{EQ-TRAIN-PRIMAL-SLACK-SOR}{{4.13}{39}}
\newlabel{EQ-TRAIN-DUAL-SLACK-SOR}{{4.15}{39}}
\newlabel{EQ-BIAS-SOR}{{4.16}{39}}
\newlabel{EQ-NEWALPHA-EQ1}{{4.21}{41}}
\newlabel{EQ-OUTPUT-MOD-SOR}{{4.22}{41}}
\newlabel{EQ-ALPHA-UPDATE-SOR1}{{4.23}{41}}
\citation{Joachims98b}
\newlabel{EQ-ERROR-UPDATE-SOR1}{{4.24}{42}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3.4}Working set methods}{42}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.4.1}QP sub-problem}{42}}
\newlabel{EQ-TRAIN-QP-MIN-FOLGA-SUB}{{4.25}{43}}
\citation{Vapnik92b}
\citation{Joachims98b}
\citation{Vanderbei94}
\citation{Osuna97a}
\citation{Platt98a}
\citation{Platt98b}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.4.2}Chunking}{44}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.4.3}$\mathrm  {SVM}^{light}${}}{44}}
\citation{Platt98a}
\citation{CRISTIANINI0001}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.3.4.4}Sequential Minimal Optimization}{45}}
\newlabel{EQ-Q-N-M}{{4.28}{46}}
\newlabel{EQ-SUM-N}{{4.29}{46}}
\newlabel{EQ-RETA-MUL-LAGR}{{4.30}{46}}
\newlabel{EQ-FULL-M-N}{{4.32}{47}}
\newlabel{EQ-BEFORE-K}{{4.38}{48}}
\newlabel{EQ-BEFORE-ERRO}{{4.39}{48}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.3}{\ignorespaces two possible placement for the equality constraint line (case a)}}{49}}
\newlabel{FIG-NOVO-VELHO-DIR}{{4.3}{49}}
\newlabel{EQ-AFTER-ERRO}{{4.41}{49}}
\newlabel{EQ-TRAIN-OLD-LINE}{{4.43}{50}}
\newlabel{EQ-TRAIN-NEW-LINE}{{4.44}{50}}
\citation{Platt98a}
\citation{KeeSheBhaMur99b}
\citation{KeeSheBhaMur99c}
\@writefile{lof}{\contentsline {figure}{\numberline {4.4}{\ignorespaces two possible placement for the equality constraint line (case b)}}{51}}
\newlabel{FIG-NOVO-VELHO-ESQ}{{4.4}{51}}
\@writefile{lot}{\contentsline {table}{\numberline {4.1}{\ignorespaces Upper and lower limits summary\relax }}{51}}
\newlabel{TAB-ALPHA-NOVO}{{4.1}{51}}
\@writefile{toc}{\contentsline {section}{\numberline {4.4}Conclusion}{52}}
\@writefile{toc}{\contentsline {chapter}{\numberline {5}The SVM-KM training strategy}{53}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{CAP-SVM-KM}{{5}{53}}
\@writefile{toc}{\contentsline {section}{\numberline {5.1}Introduction}{53}}
\citation{ANDERBERG73}
\citation{JAIN88}
\citation{JAIN9901}
\citation{Fasulo99}
\citation{JAIN9901}
\citation{MCQUENN67}
\citation{ANDERBERG73}
\citation{Lloyd82}
\citation{SELIM8401}
\@writefile{toc}{\contentsline {section}{\numberline {5.2}$k$-means}{55}}
\newlabel{SEC-K-MEANS-INTRO}{{5.2}{55}}
\citation{KOVESI0101}
\citation{PENA9901}
\newlabel{ITEM-KMSTEP1}{{1}{56}}
\newlabel{ITEM-KMSTEP2}{{2}{56}}
\newlabel{ITEM-KMSTEP3}{{3}{56}}
\newlabel{ITEM-KMSTEP4}{{4}{56}}
\citation{Scholkopf97a}
\@writefile{toc}{\contentsline {section}{\numberline {5.3}Clustering and boundaries}{57}}
\citation{Lyhyaoui99}
\citation{BARROS2000A}
\citation{dudahart73}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3.1}Modeling the boundary estimation process}{58}}
\newlabel{SEC-BOUNDARY-ESTIMATION-KM}{{5.3.1}{58}}
\newlabel{EQ-BAYES-RULE-DECISION-WEAK}{{5.1}{59}}
\citation{dudahart73}
\citation{dudahart73}
\newlabel{EQ-BAYES-SCALE}{{5.4}{60}}
\newlabel{EQ-BAYES-RULE}{{5.5}{60}}
\newlabel{EQ-BAYES-RULE-DECISION-POST}{{5.9}{61}}
\newlabel{EQ-BAYES-RULE-DECISION}{{5.10}{61}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.3.1.1}A hypothetical example}{61}}
\newlabel{EQ-PLW1}{{5.11}{61}}
\newlabel{EQ-PLW2}{{5.12}{61}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.1}{\ignorespaces Class-conditional probability density functions. Horizontal axis is represented by $\lambda $ and vertical axis is the probability.\relax }}{62}}
\newlabel{FIG-BAYES-RULE-HYPO}{{5.1}{62}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3.2}A measure for boundary estimation by $k$-means}{63}}
\newlabel{SVMKM-FEATURE-DEF}{{5.13}{63}}
\newlabel{SVMKM-FEATURE-DEF-2}{{5.14}{63}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.2}{\ignorespaces  Training set used. Support vectors are marked with a circle around training vectors.\relax }}{65}}
\newlabel{FIG-BAYESDEMODATA}{{5.2}{65}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.3}{\ignorespaces Bayes rule and $k$-means}}{66}}
\newlabel{FIG-BAYESDEMORESUL-30}{{5.3}{66}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.4}{\ignorespaces Source of the support vectors}}{67}}
\newlabel{FIG-SV2}{{5.4}{67}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.5}{\ignorespaces Source of the non-support vectors}}{67}}
\newlabel{FIG-NSV2}{{5.5}{67}}
\citation{Meila98}
\citation{Bradley98}
\citation{Phanendra93}
\citation{PENA9901}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3.3}Generalization and performance analysis}{68}}
\newlabel{SEC-KM-SPEEDUP}{{5.3.3}{68}}
\citation{UCI1998}
\newlabel{SEC-SVMKM-ADULTDATABASE}{{5.3.3}{69}}
\citation{Judd96a}
\citation{Judd96b}
\citation{Judd96a}
\citation{Fredrik00}
\@writefile{lof}{\contentsline {figure}{\numberline {5.6}{\ignorespaces Performance analysis for KM and SVM: simulation times}}{71}}
\newlabel{FIG-ALLTIMES}{{5.6}{71}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.7}{\ignorespaces Performance analysis for KM and SVM: training set size and number of support vectors}}{72}}
\newlabel{FIG-SETSIZESV}{{5.7}{72}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.8}{\ignorespaces Performance analysis for KM and SVM: generalization}}{72}}
\newlabel{FIG-GENRATE}{{5.8}{72}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.9}{\ignorespaces Performance analysis for KM and SVM: number of swaps}}{73}}
\newlabel{FIG-NUMSWAPS}{{5.9}{73}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.10}{\ignorespaces Performance analysis for KM and SVM: number of distance calculations}}{73}}
\newlabel{FIG-DISTCALC}{{5.10}{73}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.11}{\ignorespaces Performance analysis for KM and SVM: time consumed}}{74}}
\newlabel{FIG-TIMERPERITER}{{5.11}{74}}
\@writefile{lot}{\contentsline {table}{\numberline {5.1}{\ignorespaces  Simulation summary for adult database for several NCs\relax }}{74}}
\newlabel{TAB-ALLTIMES}{{5.1}{74}}
\@writefile{lot}{\contentsline {table}{\numberline {5.2}{\ignorespaces Number of swaps, distance calculations and time consumed per iteration for four different number of clusters}}{75}}
\newlabel{TAB-SWAPS}{{5.2}{75}}
\@writefile{lot}{\contentsline {table}{\numberline {5.3}{\ignorespaces Time consumed for different number of iterations in the KM training}}{76}}
\newlabel{TAB-ROUNDS-TIME}{{5.3}{76}}
\@writefile{lot}{\contentsline {table}{\numberline {5.4}{\ignorespaces Generalization for different number of iterations in the KM training}}{77}}
\newlabel{TAB-ROUNDS-GEN}{{5.4}{77}}
\citation{Pudil94}
\citation{Fukunaga72}
\citation{WebbA99}
\citation{HAYKIN9901}
\citation{NumRecipes88}
\citation{Partridge97}
\citation{Diamantaras96}
\citation{Fuka0101}
\@writefile{lof}{\contentsline {figure}{\numberline {5.12}{\ignorespaces Simulation times for only one $k$-means iteration}}{81}}
\newlabel{FIG-ALLTIMES1KM}{{5.12}{81}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.13}{\ignorespaces Generalization for adult database}}{81}}
\newlabel{FIG-GENRATE1KM}{{5.13}{81}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.14}{\ignorespaces Time spent for different number of iterations in the KM training}}{82}}
\newlabel{FIG-ROUNDS-TIME}{{5.14}{82}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.15}{\ignorespaces Generalization for different number of iterations in the KM training}}{82}}
\newlabel{FIG-ROUNDS-GEN}{{5.15}{82}}
\@writefile{lot}{\contentsline {table}{\numberline {5.5}{\ignorespaces  Generalization and training times, in seconds, for feature selection method using 321, 1043 and 1364 clusters\relax }}{83}}
\newlabel{TAB-FEATSEL}{{5.5}{83}}
\@writefile{lot}{\contentsline {table}{\numberline {5.6}{\ignorespaces  Generalization and training times, in seconds, for feature extraction method using 321, 1043 and 1364 clusters\relax }}{84}}
\newlabel{TAB-FEATEXT}{{5.6}{84}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3.4}Proposed strategies}{85}}
\newlabel{SEC-PROPOSED-STRATEGIES}{{5.3.4}{85}}
\citation{UCI1998}
\@writefile{toc}{\contentsline {section}{\numberline {5.4}Simulations}{87}}
\citation{Ziviane9601}
\citation{Marin01}
\@writefile{lot}{\contentsline {table}{\numberline {5.7}{\ignorespaces Figures organization\relax }}{89}}
\newlabel{TAB-LEGEND-1}{{5.7}{89}}
\@writefile{toc}{\contentsline {section}{\numberline {5.5}Discussion}{89}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.5.1}KM initialization time and KM time}{89}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.5.2}SVM time, training set size and SV}{90}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.5.3}Generalization and total time}{91}}
\@writefile{toc}{\contentsline {section}{\numberline {5.6}Conclusion}{92}}
\@writefile{lot}{\contentsline {table}{\numberline {5.8}{\ignorespaces Final simulation results without dimensionality reduction (A)}}{93}}
\newlabel{TAB-RESUL-FINAL-NO-DIMRED-A}{{5.8}{93}}
\@writefile{lot}{\contentsline {table}{\numberline {5.9}{\ignorespaces Final simulation results without dimensionality reduction (B)}}{94}}
\newlabel{TAB-RESUL-FINAL-NO-DIMRED-B}{{5.9}{94}}
\@writefile{lot}{\contentsline {table}{\numberline {5.10}{\ignorespaces Final simulation results with feature selection (A)}}{95}}
\newlabel{TAB-RESUL-FINAL-SELECTION-A}{{5.10}{95}}
\@writefile{lot}{\contentsline {table}{\numberline {5.11}{\ignorespaces Final simulation results with feature selection (B)}}{96}}
\newlabel{TAB-RESUL-FINAL-SELECTION-B}{{5.11}{96}}
\@writefile{lot}{\contentsline {table}{\numberline {5.12}{\ignorespaces Final simulation results with feature extraction (A)}}{97}}
\newlabel{TAB-RESUL-FINAL-EXTRACTION-A}{{5.12}{97}}
\@writefile{lot}{\contentsline {table}{\numberline {5.13}{\ignorespaces Final simulation results with feature extraction (B)}}{98}}
\newlabel{TAB-RESUL-FINAL-EXTRACTION-B}{{5.13}{98}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.16}{\ignorespaces Final simulation results without dimensionality reduction}}{99}}
\newlabel{FIG-RESUL-FINAL-NO-DIMRED}{{5.16}{99}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.17}{\ignorespaces Final simulation results with feature selection}}{100}}
\newlabel{FIG-RESUL-FINAL-SELECTION}{{5.17}{100}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.18}{\ignorespaces Final simulation results with feature extraction}}{101}}
\newlabel{FIG-RESUL-FINAL-EXTRACTION}{{5.18}{101}}
\citation{Mangasarian99}
\citation{ManMus99}
\citation{Platt98a}
\citation{Platt98b}
\citation{Joachims98b}
\citation{MUNRO9201}
\citation{CACHIN9401}
\@writefile{toc}{\contentsline {chapter}{\numberline {6}The SVM-EDR training algorithm}{103}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{CAP-SVM-EDR}{{6}{103}}
\@writefile{toc}{\contentsline {section}{\numberline {6.1}Introduction}{103}}
\citation{CACHIN9401}
\citation{barros:2001}
\citation{VALIANT84}
\citation{MITCHEL}
\citation{MICHAEL94}
\@writefile{toc}{\contentsline {section}{\numberline {6.2}Boosting}{104}}
\citation{HAUSSLER91}
\citation{KEARNS88}
\citation{KEARNS89}
\citation{KEARNS94}
\citation{SCHAPIRE90}
\citation{FREUND95}
\citation{FRESCHAP97}
\citation{SCHAPSING99}
\citation{FRESCHAP99}
\citation{FRESCHAP99}
\citation{FRESCHAP99}
\citation{SCHAPIRE99}
\citation{SCHAPSING99}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.2.1}AdaBoost algorithm}{106}}
\newlabel{EQ-SHAPIRE-ERROR}{{6.1}{106}}
\citation{LEISCH97}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces AdaBoost algorithm for binary concepts\relax }}{107}}
\newlabel{ADABOOST-ALG}{{1}{107}}
\citation{CACHIN9401}
\@writefile{lof}{\contentsline {figure}{\numberline {6.1}{\ignorespaces The $a_t$ and $\epsilon _t$ behavior.\relax }}{108}}
\newlabel{FIG-ALPHA-EPS-BEH}{{6.1}{108}}
\@writefile{toc}{\contentsline {section}{\numberline {6.3}The SVM-EDR training algorithm}{108}}
\citation{CACHIN9401}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.3.1}Error Dependent Repetition}{109}}
\newlabel{SEC-EDR-STANDARD}{{6.3.1}{109}}
\newlabel{EQ-SVMEDR-COMPAR}{{6.7}{109}}
\newlabel{EQ-SVMEDR-COMPAR-SPECIF}{{6.8}{110}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.3.2}EDR for SVMs}{110}}
\newlabel{SEC-EDR-SVM-ERROR}{{6.3.2}{110}}
\newlabel{EQ-EDR-ERROR-INDEP}{{6.9}{110}}
\@writefile{lot}{\contentsline {table}{\numberline {6.1}{\ignorespaces Eliminating class label dependence for output error.}}{110}}
\newlabel{TAB-ERRO-EDR}{{6.1}{110}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.2}{\ignorespaces Four possible placements for a training vector.\relax }}{111}}
\newlabel{FIG-ERRO-EDR}{{6.2}{111}}
\newlabel{EQ-SVMEDR-INDEP-CLASS-MIN}{{6.10}{111}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.3}{\ignorespaces Groups generated by EDR, supposing $n_E = 5$.\relax }}{112}}
\newlabel{FIG-EDR-GROUPS}{{6.3}{112}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.3.3}Understanding and estimating $n_E$}{112}}
\newlabel{SEC-ESTIMATING-NE}{{6.3.3}{112}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.3.3.1}Example 1}{112}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.4}{\ignorespaces Uniform error distribution.\relax }}{113}}
\newlabel{FIG-UNIFORM-ERROR-DISTR}{{6.4}{113}}
\newlabel{EQ-UNIFORM-TOTAL-VEC}{{6.12}{113}}
\newlabel{EQ-INTEG-UNIF}{{6.16}{114}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.5}{\ignorespaces Linear error distribution.\relax }}{115}}
\newlabel{FIG-LINEAR-ERROR-DISTR}{{6.5}{115}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.3.3.2}Example 2}{115}}
\newlabel{EQ-INTEG-LIN}{{6.20}{116}}
\citation{FRESCHAP97}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.3.3.3}Virtual training set}{117}}
\newlabel{EQ-Z-SET-SIZE}{{6.22}{117}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.3.4}SVM-EDR as a Boosting algorithm}{117}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces SVM-EDR Boosting algorithm for binary concepts\relax }}{118}}
\newlabel{EDR-BOOSTING}{{2}{118}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.3.4.1}SVMs output as a sum of weak hypothesis}{119}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {6.3.4.2}Error distribution probability convergence}{120}}
\newlabel{THEO-EDR-1}{{6.3.1}{120}}
\citation{VAPNIK9801}
\citation{Vapnik92b}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.3.5}Algorithm details}{122}}
\@writefile{toc}{\contentsline {section}{\numberline {6.4}Simulation}{123}}
\citation{SonarDB8801}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.4.1}First experiment}{124}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.4.2}Second experiment}{124}}
\@writefile{lot}{\contentsline {table}{\numberline {6.2}{\ignorespaces Results for the experiment 1, using SVMBR as training program\relax }}{124}}
\newlabel{TAB-COMP-EDR1}{{6.2}{124}}
\citation{UCI1998}
\@writefile{lot}{\contentsline {table}{\numberline {6.3}{\ignorespaces Results for the experiment 2 (Sonar), using SVMBR as training program\relax }}{125}}
\newlabel{TAB-COMP-EDR12}{{6.3}{125}}
\citation{Platt98a}
\citation{Platt98b}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.4.3}Third experiment}{126}}
\@writefile{toc}{\contentsline {section}{\numberline {6.5}Discussions}{126}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.5.1}Separation hyperplanes}{126}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.5.2}Convergence}{127}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.5.3}Training time}{128}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.5.4}Number of iterations and Z set size}{128}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.5.5}Generalization and number of support vectors}{129}}
\@writefile{toc}{\contentsline {section}{\numberline {6.6}Conclusion}{129}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.6}{\ignorespaces Training set and decision boundaries for experiment 1 using SVM-EDR}}{130}}
\newlabel{FIG-EXPEDR-1}{{6.6}{130}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.7}{\ignorespaces Training time as a function of $n_E \times e_i^x$}}{131}}
\newlabel{FIG-EDR-S1-TEMPO2D}{{6.7}{131}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.8}{\ignorespaces Number of iterations as a function of $n_E \times e_i^x$}}{132}}
\newlabel{FIG-EDR-S1-NUMIT2D}{{6.8}{132}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.9}{\ignorespaces Virtual set generated as a function of $n_E \times e_i^x$}}{133}}
\newlabel{FIG-EDR-S1-ZSIZE2D}{{6.9}{133}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.10}{\ignorespaces Generalization as a function of $n_E \times e_i^x$}}{134}}
\newlabel{FIG-EDR-S1-GENER2D}{{6.10}{134}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.11}{\ignorespaces Number of SVs as a function of $n_E \times e_i^x$}}{135}}
\newlabel{FIG-EDR-S1-NUMSV2D}{{6.11}{135}}
\@writefile{lot}{\contentsline {table}{\numberline {6.4}{\ignorespaces Results for simulation 2\relax }}{136}}
\newlabel{TAB-EDR-S1-1}{{6.4}{136}}
\@writefile{lot}{\contentsline {table}{\numberline {6.5}{\ignorespaces Results for simulation 2 (continued)\relax }}{137}}
\newlabel{TAB-EDR-S1-2}{{6.5}{137}}
\@writefile{lot}{\contentsline {table}{\numberline {6.6}{\ignorespaces Results for simulation 2 (continued)\relax }}{138}}
\newlabel{TAB-EDR-S1-3}{{6.6}{138}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.12}{\ignorespaces  Evolution of the error distribution probability for vectors belonging to $+1$ class.\relax }}{139}}
\newlabel{FIG-EDR-ERR-A-EV}{{6.12}{139}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.13}{\ignorespaces  Evolution of the error distribution probability for vectors belonging to $-1$ class.\relax }}{139}}
\newlabel{FIG-EDR-ERR-B-EV}{{6.13}{139}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.14}{\ignorespaces  Virtual set evolution for $+1$ class. Horizontal axis represents the number of iterations and vertical axis is the $Z$ size when considering only $+1$ class.\relax }}{140}}
\newlabel{FIG-EDR-ZSIZE-EV-A}{{6.14}{140}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.15}{\ignorespaces  Virtual set evolution for $-1$ class. Horizontal axis represents the number of iterations and vertical axis is the $Z$ size when considering only $-1$ class.\relax }}{140}}
\newlabel{FIG-EDR-ZSIZE-EV-B}{{6.15}{140}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.16}{\ignorespaces  Time per iteration evolution. Horizontal axis represents the number of iterations and vertical axis is the time, in seconds.\relax }}{141}}
\newlabel{FIG-EDR-TIME-EV}{{6.16}{141}}
\citation{dudahart73}
\@writefile{toc}{\contentsline {chapter}{\numberline {7}Conclusions and future works}{143}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{CAP-CONC-FUTURE}{{7}{143}}
\@writefile{toc}{\contentsline {section}{\numberline {7.1}Introduction}{143}}
\@writefile{toc}{\contentsline {section}{\numberline {7.2}The SVM-KM training strategy}{143}}
\newlabel{SEC-SVM-KM-CONC}{{7.2}{143}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.2.1}Boundary estimation by $k$-means}{144}}
\citation{Judd96a}
\citation{Judd96b}
\citation{Fuka0101}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.2.2}Speeding up KM}{146}}
\citation{Fredrik00}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.2.3}Generalization and performance analysis}{147}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.2.4}Performance of the proposed strategies}{147}}
\@writefile{toc}{\contentsline {section}{\numberline {7.3}The SVM-EDR training algorithm}{149}}
\newlabel{SEC-SVM-EDR-CONC}{{7.3}{149}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.3.1}SVM-EDR implementation}{149}}
\newlabel{EQ-SVMEDR-EQ-CONC}{{7.1}{150}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.3.2}Virtual training set and Boosting}{150}}
\citation{FRESCHAP97}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.3.3}Convergence of SVM-EDR}{151}}
\citation{VAPNIK9801}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.3.4}Separation hyperplanes}{152}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.3.5}Training time}{152}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.3.6}Number of iterations and Z set size}{153}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.3.7}Generalization and number of support vectors}{153}}
\@writefile{toc}{\contentsline {section}{\numberline {7.4}Future works}{154}}
\newlabel{SEC-FUTURE-WORKS}{{7.4}{154}}
\citation{Vapnik92b}
\bibdata{bibtex/neural,bibtex/svm,bibtex/boosting}
\bibcite{BOSER92a}{1}
\bibcite{VAPNIK9501}{2}
\bibcite{VAPNIK9801}{3}
\bibcite{CRISTIANINI0001}{4}
\bibcite{CAMPBELL0201}{5}
\bibcite{Drucker99}{6}
\bibcite{Barzilay99}{7}
\bibcite{KIM0201}{8}
\@writefile{toc}{\contentsline {chapter}{Bibliography}{157}}
\bibcite{Brown00}{9}
\bibcite{VALENTINI0201}{10}
\bibcite{Joachims98}{11}
\bibcite{DISTANTE0301}{12}
\bibcite{KOTROPOULOS0301}{13}
\bibcite{SHAONING0301}{14}
\bibcite{WANG0201}{15}
\bibcite{JEFFREY0201}{16}
\bibcite{LOO0201}{17}
\bibcite{MCQUENN67}{18}
\bibcite{ANDERBERG73}{19}
\bibcite{Lloyd82}{20}
\bibcite{BARROS2000A}{21}
\bibcite{dudahart73}{22}
\bibcite{CACHIN9401}{23}
\bibcite{Luenberger86}{24}
\bibcite{barros:2001}{25}
\bibcite{VLADIMIR9801}{26}
\bibcite{WING9101}{27}
\bibcite{HAYKIN9901}{28}
\bibcite{VAPNIK8201}{29}
\bibcite{Burges98}{30}
\bibcite{COVER6501}{31}
\bibcite{BAZARAA7901}{32}
\bibcite{COURANT7001}{33}
\bibcite{Kaufmann99}{34}
\bibcite{Platt98b}{35}
\bibcite{SMOBR}{36}
\bibcite{SteveGun2000}{37}
\bibcite{NetLib2000}{38}
\bibcite{Vanderbei94}{39}
\bibcite{Suykens99a}{40}
\bibcite{LAWSON9501}{41}
\bibcite{Keerthi99b}{42}
\bibcite{Zhang99a}{43}
\bibcite{Adatron98}{44}
\bibcite{FriCriCam98}{45}
\bibcite{Mangasarian99}{46}
\bibcite{ManMus99}{47}
\bibcite{Joachims98b}{48}
\bibcite{Vapnik92b}{49}
\bibcite{Osuna97a}{50}
\bibcite{Platt98a}{51}
\bibcite{KeeSheBhaMur99b}{52}
\bibcite{KeeSheBhaMur99c}{53}
\bibcite{JAIN88}{54}
\bibcite{JAIN9901}{55}
\bibcite{Fasulo99}{56}
\bibcite{SELIM8401}{57}
\bibcite{KOVESI0101}{58}
\bibcite{PENA9901}{59}
\bibcite{Scholkopf97a}{60}
\bibcite{Lyhyaoui99}{61}
\bibcite{Meila98}{62}
\bibcite{Bradley98}{63}
\bibcite{Phanendra93}{64}
\bibcite{UCI1998}{65}
\bibcite{Judd96a}{66}
\bibcite{Judd96b}{67}
\bibcite{Fredrik00}{68}
\bibcite{Pudil94}{69}
\bibcite{Fukunaga72}{70}
\bibcite{WebbA99}{71}
\bibcite{NumRecipes88}{72}
\bibcite{Partridge97}{73}
\bibcite{Diamantaras96}{74}
\bibcite{Fuka0101}{75}
\bibcite{Ziviane9601}{76}
\bibcite{Marin01}{77}
\bibcite{MUNRO9201}{78}
\bibcite{VALIANT84}{79}
\bibcite{MITCHEL}{80}
\bibcite{MICHAEL94}{81}
\bibcite{HAUSSLER91}{82}
\bibcite{KEARNS88}{83}
\bibcite{KEARNS89}{84}
\bibcite{KEARNS94}{85}
\bibcite{SCHAPIRE90}{86}
\bibcite{FREUND95}{87}
\bibcite{FRESCHAP97}{88}
\bibcite{SCHAPSING99}{89}
\bibcite{FRESCHAP99}{90}
\bibcite{SCHAPIRE99}{91}
\bibcite{LEISCH97}{92}
\bibcite{SonarDB8801}{93}
\bibstyle{unsrt}
\@writefile{toc}{\contentsline {chapter}{\numberline {A}SVMBR program overview}{169}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{SVMBR-PROGRAMA}{{A}{169}}
\@writefile{toc}{\contentsline {section}{\numberline {A.1}Introduction}{169}}
\@writefile{toc}{\contentsline {section}{\numberline {A.2}Internal structure}{169}}
\@writefile{toc}{\contentsline {section}{\numberline {A.3}Using SVMBR}{170}}
\@writefile{toc}{\contentsline {section}{\numberline {A.4}SVMBR use summary}{174}}
\newlabel{SEC-SVM-USAGE}{{A.4}{174}}
\ttl@finishall
\@writefile{lof}{\contentsline {figure}{\numberline {A.1}{\ignorespaces SVMBR packages.\relax }}{182}}
\newlabel{FIG-UML-PACKAGES}{{A.1}{182}}
\@writefile{lof}{\contentsline {figure}{\numberline {A.2}{\ignorespaces Data package class structure.\relax }}{183}}
\newlabel{FIG-UML-DATA}{{A.2}{183}}
\@writefile{lof}{\contentsline {figure}{\numberline {A.3}{\ignorespaces Kernel package class structure.\relax }}{184}}
\newlabel{FIG-UML-KERNEL}{{A.3}{184}}
\@writefile{lof}{\contentsline {figure}{\numberline {A.4}{\ignorespaces Solver package class structure.\relax }}{185}}
\newlabel{FIG-UML-SOLVER}{{A.4}{185}}
\@writefile{lof}{\contentsline {figure}{\numberline {A.5}{\ignorespaces SVM package class structure.\relax }}{186}}
\newlabel{FIG-UML-SVM}{{A.5}{186}}
